{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Reach a Number"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: reachNumber"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #到达终点数字"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>在一根无限长的数轴上，你站在<code>0</code>的位置。终点在<code>target</code>的位置。</p>\n",
    "\n",
    "<p>你可以做一些数量的移动 <code>numMoves</code> :</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>每次你可以选择向左或向右移动。</li>\n",
    "\t<li>第 <code>i</code>&nbsp;次移动（从 &nbsp;<code>i == 1</code>&nbsp;开始，到&nbsp;<code>i == numMoves</code> ），在选择的方向上走 <code>i</code>&nbsp;步。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给定整数&nbsp;<code>target</code> ，返回 <em>到达目标所需的 <strong>最小&nbsp;</strong>移动次数(即最小 <code>numMoves</code> )&nbsp;</em>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> target = 2\n",
    "<strong>输出:</strong> 3\n",
    "<strong>解释:</strong>\n",
    "第一次移动，从 0 到 1 。\n",
    "第二次移动，从 1 到 -1 。\n",
    "第三次移动，从 -1 到 2 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> target = 3\n",
    "<strong>输出:</strong> 2\n",
    "<strong>解释:</strong>\n",
    "第一次移动，从 0 到 1 。\n",
    "第二次移动，从 1 到 3 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>-10<sup>9</sup>&nbsp;&lt;= target &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>target != 0</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [reach-a-number](https://leetcode.cn/problems/reach-a-number/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [reach-a-number](https://leetcode.cn/problems/reach-a-number/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['2', '3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachNumber(self, target: int) -> int:\n",
    "        target=abs(target)\n",
    "        k=0\n",
    "        while target>0:\n",
    "            k+=1\n",
    "            target-=k\n",
    "        if target%2==0:\n",
    "            return k\n",
    "        else:\n",
    "            return k+1+k%2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachNumber(self, target: int) -> int:\n",
    "        target = abs(target)\n",
    "        s = n = 0\n",
    "        while s < target or (s - target) % 2:  # 没有到达（越过）终点，或者相距奇数\n",
    "            n += 1\n",
    "            s += n\n",
    "        return n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def reachNumber(self, target: int) -> int:\n",
    "        target=abs(target)\n",
    "        x=int(math.sqrt(2*abs(target)))-1\n",
    "        while 1:\n",
    "            if x*(x+1)/2<abs(target):\n",
    "                x=x+1\n",
    "            elif (x*(x+1)/2-target)%2==0:\n",
    "                return x\n",
    "            else:\n",
    "                x=x+1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachNumber(self, target: int) -> int:\n",
    "        k = abs(target)\n",
    "        n = math.ceil((-1 + math.sqrt(1 + 8 * k)) / 2)\n",
    "        return n if (n * (n + 1) / 2 - k) % 2 == 0 else n + 1 + n % 2\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachNumber(self, target: int) -> int:\n",
    "        # 1 2 3 = 6\n",
    "        # 1 -2 3 = 2\n",
    "        # n*(n + 1) // 2 >= target\n",
    "        # n^2 + n - 2*target = 0\n",
    "        target = abs(target)\n",
    "        \n",
    "        n = ceil((-1 + sqrt(1 + 8*target))/ 2)\n",
    "        \n",
    "        return n if (n*(n + 1) // 2 - target) % 2 == 0 else n + 1 + n % 2 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachNumber(self, target: int) -> int:\n",
    "        target = -target if target < 0 else target\n",
    "        l, r = 1, int(1e9 + 1)\n",
    "        while l <= r:\n",
    "            m = (l + r) // 2\n",
    "            if m * (m + 1) < 2 * target:\n",
    "                l = m + 1\n",
    "            else:\n",
    "                r = m - 1\n",
    "        \n",
    "        while (l * (l + 1) // 2 + target) % 2:\n",
    "            l += 1\n",
    "        return l\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachNumber(self, target: int) -> int:\n",
    "        n = ceil(sqrt(2 * abs(target) + 0.25) - 0.5)\n",
    "        return n if (n * (n + 1) // 2 - abs(target)) % 2 == 0 else n + 1 + n % 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachNumber(self, target: int) -> int:\n",
    "        n = ceil(sqrt(2 * abs(target) + 0.25) - 0.5)\n",
    "        return n if (n * (n + 1) // 2 - abs(target)) % 2 == 0 else n + 1 + n % 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachNumber(self, target: int) -> int:\n",
    "        target = abs(target)\n",
    "        k = 0\n",
    "        while target > 0 :\n",
    "            k += 1\n",
    "            target -= k\n",
    "        return k if target % 2 == 0 else k + 1 + k % 2\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachNumber(self, target: int) -> int:\n",
    "        target = abs(target)\n",
    "        sum = 0\n",
    "        i = 1\n",
    "        while True:\n",
    "            sum += i\n",
    "            if sum>= target and (sum - target)%2==0:\n",
    "                return i\n",
    "            i += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachNumber(self, target: int) -> int:\n",
    "        target = abs(target)\n",
    "        s = n = 0\n",
    "        # 没有走到终点就继续走，相距奇数\n",
    "        while s < target or (s-target)%2:\n",
    "            n += 1\n",
    "            s += n\n",
    "        return n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachNumber(self, target: int) -> int:\n",
    "        ans = 0\n",
    "        if target < 0:target = -target\n",
    "        total = 0\n",
    "        i = 1\n",
    "        while total < target:\n",
    "            total +=i\n",
    "            i += 1\n",
    "        if target == total:return i-1\n",
    "        diff = total - target\n",
    "        if diff%2 == 1:\n",
    "            if i % 2 == 1:return i\n",
    "            else:return i+1\n",
    "        if diff%2 == 0:return i-1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachNumber(self, target: int) -> int:\n",
    "        end=abs(target)\n",
    "        if end%2==0:\n",
    "            i=0\n",
    "            while i*(i+1)//2<end:\n",
    "                i+=1\n",
    "            if i%4==3 or i%4==0:\n",
    "                return i\n",
    "            elif i%4==1:\n",
    "                return i+2\n",
    "            else:\n",
    "                return i+1\n",
    "        else:\n",
    "            i=0\n",
    "            while i*(i+1)//2<end:\n",
    "                i+=1\n",
    "            if i%4==1 or i%4==2:\n",
    "                return i\n",
    "            elif i%4==3:\n",
    "                return i+2\n",
    "            else:\n",
    "                return i+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachNumber(self, target: int) -> int:\n",
    "        target = abs(target)\n",
    "        s = n = 0\n",
    "        while s < target or (s-target) % 2:\n",
    "            n += 1\n",
    "            s += n\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachNumber(self, target: int) -> int:\n",
    "        # 归纳\n",
    "        target = abs(target)\n",
    "        s = n = 0\n",
    "        while s < target or (s - target) % 2: #没有到达(越过终点， 或者相聚奇数\n",
    "            n += 1\n",
    "            s += n \n",
    "        return n \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachNumber(self, target: int) -> int:\n",
    "        target = abs(target)\n",
    "        n = ((target*8+1)**0.5-1)/2\n",
    "        if n-int(n) == 0:\n",
    "            return int(n)\n",
    "        n = int(n)\n",
    "        k = n % 4\n",
    "        if target % 2 == 0:\n",
    "            if k == 3:\n",
    "                return n+1\n",
    "            elif k == 2:\n",
    "                return n+1\n",
    "            elif k == 1:\n",
    "                return n+2\n",
    "            else:\n",
    "                return n+3\n",
    "        else:\n",
    "            if k == 1:\n",
    "                return n+1\n",
    "            elif k == 0:\n",
    "                return n+1\n",
    "            elif k == 3:\n",
    "                return n+2\n",
    "            else:\n",
    "                return n+3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachNumber(self, target: int) -> int:\n",
    "        target = abs(target)\n",
    "        s = k = 0\n",
    "        while 1:\n",
    "            if s >= target and (s - target) % 2 == 0:\n",
    "                return k\n",
    "            k += 1\n",
    "            s += k\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachNumber(self, target: int) -> int:\n",
    "        target = abs(target)\n",
    "        k = 0\n",
    "        while target > 0:\n",
    "            k += 1\n",
    "            target -= k\n",
    "        return k if target % 2 == 0 else k + 1 + k % 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachNumber(self, target: int) -> int:\n",
    "        target = abs(target)\n",
    "        res, ssum = 0, 0\n",
    "        while ssum < target or (ssum - target) % 2 != 0:\n",
    "            res += 1\n",
    "            ssum += res\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachNumber(self, target: int) -> int:\n",
    "        target = abs(target)\n",
    "        k = 0\n",
    "        while target > 0:\n",
    "            k += 1\n",
    "            target -= k\n",
    "        return k if target % 2 == 0 else k + 1 + k % 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachNumber(self, target: int) -> int:\n",
    "        n = ceil(sqrt(2 * abs(target) + 0.25) - 0.5)\n",
    "        return n if (n * (n + 1) // 2 - abs(target)) % 2 == 0 else n + 1 + n % 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachNumber(self, target: int) -> int:\n",
    "        target = abs(target)\n",
    "        k = 0\n",
    "        while target > 0 :\n",
    "            k += 1\n",
    "            target -= k\n",
    "        return k if target % 2 == 0 else k + 1 + k % 2\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\r\n",
    "class Solution:\r\n",
    "    def reachNumber(self, target: int) -> int:\r\n",
    "        target=abs(target)\r\n",
    "        left,right=0,target+1\r\n",
    "        # s=0\r\n",
    "        while left<right:\r\n",
    "            mid=(left+right)//2\r\n",
    "            s=(1+mid)*mid//2\r\n",
    "            if s==target:\r\n",
    "                return mid\r\n",
    "            elif s<target:\r\n",
    "                left=mid+1\r\n",
    "            else:\r\n",
    "                right=mid\r\n",
    "        s=(1+left)*left//2\r\n",
    "        if (s-target)%2==0:\r\n",
    "            return left\r\n",
    "        else:\r\n",
    "            return left+1+left%2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachNumber(self, target: int) -> int:\n",
    "        n = ceil((2 * abs(target)) ** 0.5 - 0.5)     \n",
    "        s = ceil(n / 2)\n",
    "        j = s - target\n",
    "        if j % 2 == 0:\n",
    "            return n\n",
    "        else:\n",
    "            return n + 1 + n % 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachNumber(self, target: int) -> int:\n",
    "        import math\n",
    "        n = math.ceil((2 * abs(target) + 0.25) ** 0.5 - 0.5)     \n",
    "        s = n * (n + 1) // 2\n",
    "        j = (s - target)\n",
    "        \n",
    "        if j % 2 == 0:\n",
    "            return n\n",
    "        else:\n",
    "            return n + 2 - (n + 1) % 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachNumber(self, target: int) -> int:\n",
    "        ans = 0\n",
    "        if target < 0:target = -target\n",
    "        total = 0\n",
    "        i = 1\n",
    "        while total < target:\n",
    "            total +=i\n",
    "            i += 1\n",
    "        diff = total - target\n",
    "        if diff%2 == 1:\n",
    "            if i % 2 == 1:return i\n",
    "            else:return i+1\n",
    "        if diff%2 == 0:return i-1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachNumber(self, target: int) -> int:\n",
    "        target = abs(target)\n",
    "        ans = 0\n",
    "        step = 0\n",
    "\n",
    "        while True:\n",
    "            s = (ans * ans + ans) // 2\n",
    "\n",
    "            if s == target or (s > target and (s - target) % 2 == 0):\n",
    "                return ans\n",
    "\n",
    "            ans = ans + 1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachNumber(self, target: int) -> int:\n",
    "        n = 0\n",
    "        while n * (n + 1)//2 < abs(target):\n",
    "            n += 1\n",
    "            \n",
    "        s = n * (n + 1) // 2\n",
    "        j = (s - target)\n",
    "        \n",
    "        if j % 2 == 0:\n",
    "            return n\n",
    "        else:\n",
    "            if (n + 1) % 2 == 1:\n",
    "                return n + 1\n",
    "            else:\n",
    "                return n + 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachNumber(self, target: int) -> int:\n",
    "        target = abs(target)\n",
    "        ans = 0\n",
    "        total = 0\n",
    "        while True:\n",
    "            ans += 1\n",
    "            total += ans\n",
    "            if total >= target and (total - target) % 2 == 0:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachNumber(self, target: int) -> int:\n",
    "        n = ceil(sqrt(2 * abs(target)) - 0.5)     \n",
    "        s = ceil(n / 2)\n",
    "        j = s - target\n",
    "        if j % 2 == 0:\n",
    "            return n\n",
    "        else:\n",
    "            return n + 1 + n % 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachNumber(self, target: int) -> int:\n",
    "        n = ceil(sqrt(2 * abs(target)) - 0.5)     \n",
    "        s = ceil(n / 2)\n",
    "        j = s - target\n",
    "        if j % 2 == 0:\n",
    "            return n\n",
    "        else:\n",
    "            return n + 1 + n % 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import Queue\n",
    "class Solution:\n",
    "    def reachNumber(self, target: int) -> int:\n",
    "        \"\"\"\n",
    "        本质上是1~numMoves中添加负号使得其等于target\n",
    "        例如 1-2+3+4-5+...+numMoves=target\n",
    "        BFS会超时 下面用数学的方法求解\n",
    "        有如下几种情况：0 1 3 6 10 15\n",
    "        1.全部都前进 刚好到，比如10=1+2+3+4\n",
    "        2.越过终点，距离终点偶数，如target=8 此时如果距离为2则第一步反向走，为4则第二步 依次类推...\n",
    "        3.越过终点，距离终点奇数，如target=7 此时再多走一步 如果相距为偶数则转2 否则转4\n",
    "        4.越过终点多走一步仍为奇数，如target=5 直接多走两部 必然变为偶数\n",
    "        证明，为啥4中假设成立？\n",
    "        因为此时相距为奇数 走两步 奇数加上两个相邻（必定一奇一偶） 显然是偶数\n",
    "        \"\"\"\n",
    "        target = abs(target) #小于0 可以转换为大于0处理\n",
    "        s = 0\n",
    "        steps = 0\n",
    "        while s<target or (s-target)%2:# 没有到达（越过）终点，或者相距奇数\n",
    "            steps += 1\n",
    "            s += steps\n",
    "        return steps\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachNumber(self, target: int) -> int:\n",
    "        target= abs(target)\n",
    "        i = 1\n",
    "        now = 0\n",
    "        while(now<target):\n",
    "            now+=i\n",
    "            i+=1\n",
    "\n",
    "        return i - 1 if (now - target) % 2 == 0 else i + (i-1)%2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachNumber(self, target: int) -> int:\n",
    "        n = ceil(sqrt(2 * abs(target)) - 0.5)     \n",
    "        s = ceil(n / 2)\n",
    "        j = s - target\n",
    "        if j % 2 == 0:\n",
    "            return n\n",
    "        else:\n",
    "            return n + 1 + n % 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachNumber(self, target: int) -> int:\n",
    "        target = abs(target)\n",
    "        s = n = 0\n",
    "        while s < target or (s - target) % 2:\n",
    "            n += 1\n",
    "            s += n\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachNumber(self, target: int) -> int:\n",
    "        target = abs(target)\n",
    "\n",
    "        s = 0\n",
    "        n = 0\n",
    "\n",
    "        while s < target or (s - target) % 2:\n",
    "            n += 1\n",
    "            s += n\n",
    "        \n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachNumber(self, target: int) -> int:\n",
    "        import math\n",
    "        n = math.ceil((2 * abs(target) + 0.25) ** 0.5 - 0.5)     \n",
    "        s = n * (n + 1) // 2\n",
    "        j = (s - target)\n",
    "        \n",
    "        if j % 2 == 0:\n",
    "            return n\n",
    "        else:\n",
    "            if (n + 1) % 2 == 1:\n",
    "                return n + 1\n",
    "            else:\n",
    "                return n + 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachNumber(self, target: int) -> int:\n",
    "        n = ceil((2 * abs(target)) ** 0.5 - 0.5)     \n",
    "        s = ceil(n/2)\n",
    "        j = (s - target)\n",
    "        if j % 2 == 0:\n",
    "            return n\n",
    "        else:\n",
    "            return n + 1 + n % 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachNumber(self, target: int) -> int:\n",
    "        target = abs(target)\n",
    "        n = ceil((-1 + (8 * target + 1) ** 0.5) / 2)\n",
    "        return n if (n * (n + 1) // 2 - target) % 2 == 0 else n + 1 + n % 2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachNumber(self, target: int) -> int:\n",
    "        n = ceil(sqrt(8 * abs(target) + 1)/2 - 0.5) \n",
    "        return n if (n * (n + 1) // 2 - abs(target)) % 2 == 0 else n + 1 + n % 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachNumber(self, target: int) -> int:\n",
    "        n = ceil(sqrt(2 * abs(target)) - 0.5)     \n",
    "        s = ceil(n / 2)\n",
    "        j = s - target\n",
    "        if j % 2 == 0:\n",
    "            return n\n",
    "        else:\n",
    "            return n + 1 + n % 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachNumber(self, target: int) -> int:\n",
    "        import math\n",
    "        n = math.ceil((2 * abs(target) + 0.25) ** 0.5 - 0.5)     \n",
    "        s = math.ceil(n/2)\n",
    "        j = (s - target)\n",
    "        if j % 2 == 0:\n",
    "            return n\n",
    "        else:\n",
    "            return n + 2 - (n + 1) % 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachNumber(self, target: int) -> int:\n",
    "        import math\n",
    "        n = math.ceil((2 * abs(target)) ** 0.5 - 0.5)     \n",
    "        s = math.ceil(n/2)\n",
    "        j = (s - target)\n",
    "        if j % 2 == 0:\n",
    "            return n\n",
    "        else:\n",
    "            return n + 1 + n % 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachNumber(self, target: int) -> int:\n",
    "        import math\n",
    "        n = math.ceil((2 * abs(target)) ** 0.5 - 0.5)     \n",
    "        s = math.ceil(n/2)\n",
    "        j = (s - target)\n",
    "        if j % 2 == 0:\n",
    "            return n\n",
    "        else:\n",
    "            return n + 1 + n % 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachNumber(self, target: int) -> int:\n",
    "        import math\n",
    "        n = math.ceil((2 * abs(target)) ** 0.5 - 0.5)     \n",
    "        s = math.ceil(n/2)\n",
    "        j = (s - target)\n",
    "        if j % 2 == 0:\n",
    "            return n\n",
    "        else:\n",
    "            return n + 2 - (n + 1) % 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachNumber(self, target: int) -> int:\n",
    "        import math\n",
    "        n = math.ceil((2 * abs(target)) ** 0.5 - 0.5)     \n",
    "        s = math.ceil(n/2)\n",
    "        j = (s - target)\n",
    "        if j % 2 == 0:\n",
    "            return n\n",
    "        else:\n",
    "            return n + 2 - (n + 1) % 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachNumber(self, target: int) -> int:\n",
    "        target = abs(target)\n",
    "        k = 0\n",
    "        sum_k = 0\n",
    "\n",
    "        while sum_k < target or (sum_k - target) % 2 != 0:\n",
    "            k += 1\n",
    "            sum_k += k\n",
    "        \n",
    "        return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachNumber(self, target: int) -> int:\n",
    "        target = abs(target)\n",
    "        s = n = 0\n",
    "        while s < target:\n",
    "            n += 1\n",
    "            s += n\n",
    "        if s - target == 0: return n\n",
    "        elif (s - target) % 2 == 0: return n\n",
    "        elif n % 2 == 0: return n +1\n",
    "        else: return n + 2"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
